MPRI 1.24 - Randomized Algorithms - Nicolas Schabanel
Lecture 3 (Part B/C): Thursday Feb 6, 8:45-11:45 - Streaming, Property testing, Self-correction
• Streaming algorithm for computing the second moment of frequencies F2 : 4-wise independent hash functions
• Self-correcting integer product
Exercise session 3: PDF Due on Thursday Feb 13 before noon
• A Fixed Parameter Tractable algorithm for finding k disjoints triangles
• A deterministic algorithm for uniformity dectection
• Matrix multiplication testing
